package codeTop.简单;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 挚爱之夕
 * @date 2021/9/23 - 09 - 23 - 11:22
 * @Description: codeTop
 * @Version: 1.0
 */
public class _004_相交链表 {
    public static void main(String[] args) {
        ListNode l3 = new ListNode(6,null);
        ListNode l2 = new ListNode(4,l3);
        ListNode l1 = new ListNode(2,l2);
        ListNode r2 = new ListNode(1,l3);
        ListNode r1 = new ListNode(0,r2);
        ListNode ans = getIntersectionNode(l1,r1);
        System.out.println(ans.val);
    }
    //哈希集合
    private static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode cur = headA;
        while(cur!=null){
            set.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while(cur!=null){
            if(!set.add(cur)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //双指针
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    private static void printList(ListNode head){
        while(head!=null){
            System.out.print(head.val+"->");
            head = head.next;
        }
        System.out.print("null");
    }
}
